package a.codetop.笔试框架.天王;

import org.junit.Test;

public class 迷宫2_是否存在_查找单词_y总 {

    @Test
    public void test() {
        char[][] g={
                {'A','B','C','A'},
                {'S','F','C','S'},
                {'A','D','E','E'}
        };
        System.out.println("有BCCEE吗: "+hasDanci(g, "BCCEE"));
    }
    //main↑————————————————————————————————————————————————————————————————————————————————————————————————————

    //所求
    boolean res=false;

    public boolean hasDanci(char[][] g, String str) {
        for(int i=0;i<g.length;i++){
            for(int j=0;j<g[0].length;j++){
                if(g[i][j]==str.charAt(0)){
                    //System.out.println("起点:"+g[i][j]);
                    migong(g,i,j, str,0);
                    if(res==true)return true;
                    //还原dfs的全局变量
                    res=false;
                }
            }
        }
        return false;
    }

    int[][] fx={{-1,0},{1,0},{0,-1},{0,1}};

    public void migong(char[][] g,int i,int j, String str, int u){
        pt(g);

        //(找到一个就不再递归了)
        if(res==true)return;
        //2、终点（因为下方是预判，所以这里ij是一定满足条件的，即只要ij判断到n-1即判断完毕了）
        if(u==str.length()-1){
            res=true;
            return;
        }

        for(int k=0;k<4;k++){
            int x=i+fx[k][0], y=j+fx[k][1];
            //1、预判xy
            if(
                x<0||x>=g.length||y<0||y>=g[0].length|| g[x][y]=='*' //越界+走过
                || u+1<str.length()&&g[x][y]!=str.charAt(u+1) //其他不能走的情况
            )continue;
            //3、放心迭代xy
            char t=g[i][j];g[i][j]='*';
            migong(g,x,y, str,u+1);
            g[i][j]=t;
        }
    }

    //debug↓————————————————————————————————————————————————————————————————————————————————————————————————————
    void pt(char[][] g){
        for (int i = 0; i < g.length; i++) {
            for (int j = 0; j < g[0].length; j++) {
                System.out.print(String.format("%3s",g[i][j]));
            }
            System.out.println();
        }
        System.out.println("——————————————————————————");
    }
}
